\section{Previous work}

Before inlining was applied to so-called ``structured programming
languages'', the technique was applied to languages such as Fortran,
that do not allow recursion, and therefore do not need for subroutines
to allocate their own environments upon entry.  And it was then
referred to as ``open-coding of subroutines''.  Scheifler
\cite{Scheifler:1977:AIS:359810.359830} is probably one of the first
to apply inlining to more modern programming languages.  The language
used by Scheifler is CLU \cite{Liskov:1977:AMC:359763.359789}.

Ayers et al \cite{Ayers:1997:AI:258915.258928} consider the benefit of
inlining consisting of the elimination of the overhead of a procedure
call to be a ``side benefit'', and we agree.  They cite the main
benefit as the opportunity for more optimizing code transformations
when the code of the called function is exposed in the context of the
calling function.

In their paper, they also mention \emph{cloning} as an alternative to
inlining, i.e., the duplication and specialization of the called
function according to the context of the calling function.  However,
they consider inlining to be strictly superior to cloning in terms of
the possible additional optimizations made possible, so they recommend
cloning only as a means to avoid too large an increase in the code
size, which could slow down subsequent non-linear optimizations.
Cloning, and especially the specialization of the cloned code in the
context of the caller, is one technique used in \emph{partial
  evaluation} \cite{Jones:1993:PEA:153676}.  Inlining, however,
whether total or partial, is not a technique of partial evaluation.
Inlining may of course enable such techniques by exposing the code of
the called function in the context of the caller.

Most existing work is concerned with determining when inlining is to
be performed, based on some analysis of the benefits as compared to
the penalties in terms of increased compilation time in subsequent
optimization passes.  The inlining technique itself is considered
trivial, or in the words of Chang and Hwu
(\cite{Chang:1989:IFE:73141.74840, Chang:1989:IFE:74818.74840}) ``The
work required to duplicate the callee is trivial''.  Inlining might be
trivial in the context of purely function programming, in that it
suffices to replace occurrences of local variables in the called
function by the argument expressions in the function call.  However,
for a language such as \commonlisp{} that allows for assignments to
lexical variables, inlining can be non-trivial.  Consider the
following example:

\begin{verbatim}
(defun f (x y) (setq x y))

(defun g (a) (f a 3) a)
\end{verbatim}

If simple renaming is applied, we obtain the following code which does
not preserve the semantics of the original code:

\begin{verbatim}
(defun g (a) (setq a 3) a)
\end{verbatim}

\noindent
The use of continuation-passing style for compiling \commonlisp{}
programs often requires a priori elimination of side effects by
confiding these side effects to updates on \emph{cells}.  Such a
conversion transforms the program so that it respects a purely
functional style, making inlining trivial as indicated above.
However, such a conversion has a significant impact on program
performance, especially in the context of modern processors, where
memory access are orders of magnitude more expensive than register
operations.

Because of issues such as this one, this paper discusses only a
technique for inlining in the context of arbitrary \commonlisp{} code
that might contain such side effects.  It does not discuss the more
complex issue of determining a strategy for when inlining should or
should not be applied.

Although the paper by Ayers et al explains that their technique is
applied to intermediate code, just like the technique that we present
in this paper, their paper contains little information about the details
of their technique.

%%  LocalWords:  inlining optimizations
